#include <unordered_set>
#include <vector>
#include <iostream>
using namespace std;
// // 5, 6, 8, 6, 9, 1, 6, 1, 2, 4, 9, 1, 9, 8, 2, 3, 6, 4, 7, 7, 5, 9, 5,
// // 0, 3, 8, 7, 5, 8, 1, 5, 8, 6, 1, 8, 3, 0, 3, 7, 9, 2,
// // 7, 0, 5, 8, 8, 5, 7, 0, 9, 9, 1, 9, 4, 4, 6, 8, 6, 3, 
// 3, 8, 5, 1, 6, 3, 4, 6, 7, 0, 7, 8, 2, 7, 6, 8, 9, 5,
// 6, 5, 6, 1, 4, 0, 1, 0, 0, 9, 4, 8, 0, 9, 1, 2, 8, 5,
// 0, 2, 5, 3, 3
vector<int>arr = {
3, 8, 5, 1, 6, 3, 4, 6, 7, 0, 7, 8, 2, 7, 6, 8, 9, 5,
6, 5, 6, 1, 4, 0, 1, 0, 0, 9, 4, 8, 0, 9, 1, 2, 8, 5,
0, 2, 5, 3, 3
};
int nums[] = {0,31,28,31,30,31,30,31,31,30,31,30,31};
unordered_set<int> window;
int ans = 0;

bool check(int a,int b,int c,int d){
  int mon = a * 10 + b,day = c*10 + d;
  if(mon < 1 || mon > 12){
    return false;
  }
  if(day < 1 || day > nums[mon]){
    return false;
  }
  if(window.count(mon * 100 + day)){
    return false;
  }
  // cout << mon <<' ' << day << endl;
  window.insert(mon * 100 + day);
  return true;
}
// 1 23
// 1 24
// 1 25
// 1 26
// 1 27
// 1 28
// 1 29
// 1 30
// 1 31
// 9
int main(){
  for(int i = 0;i < arr.size();i++){
    for(int j = i + 1;j < arr.size();j++){
        for(int k = j + 1;k < arr.size();k++){
          for(int n = k + 1;n < arr.size();n++){
            if(check(arr[i],arr[j],arr[k],arr[n])){
              ans++;
            }
          }
        }
    }
  }
  cout << ans << endl;
  return 0;
}
// bool find(int a){

// }
// int main(){
//   unordered_set<int> window;
//   for(int i = 0;i  < 99;i++){
//     int a = arr[i];
//     if(cnt4 == false){
//       if(a == 2 &&cnt1 == false){
//           cnt1 = true;
//       }
//       else if(a == 0 && cnt2 == false){
//           cnt2 = true;
//       }
//       else if(a == 2 &&cnt3 == false){
//           cnt3 = true;
//       }
//       else if(a == 3 &&cnt4 == false){
//           cnt4 = true;
//       }
//     }else{
//       if(find(a)){
//         ans++;
//       }
//       cnt[a]++;
//     }
//   }  
// }

#include<iostream>
#include<cmath>
using namespace std;
int main(){
  double mode = 11625907.5798;
  int len = 23333333;
  double tmp = log(2);
//  cout << tmp << endl;
  int cnt0 = 0,cnt1 = len;
  // int len = 3,cnt0 = 1,cnt1 = 2;
  while(cnt0 < cnt1){
    double a = (double)cnt0 / len;
    double b = (double)cnt1 / len;
    double h = - a * cnt0 * log(a) / tmp -  b * cnt1 * log(b) / tmp;
    if(abs(mode - h) < 0.0001){
      cout << cnt0 << endl;
      break;
     }
    cnt1--;cnt0++;
  }
  return 0;
}
#include<iostream>
using namespace std;
// int a[10005];
// int b[10005];
int main(){
  int n;  cin>>n;
      int ansmax = 10000000,ansmin = 0;
  for(int i = 0;i < n;i++){
    int a, b;
    cin >> a >> b;
    ansmax = min(a/b,ansmax);
    ansmin = max(a/(b + 1) + 1,ansmin); 
  }
  cout << ansmin <<' ' << ansmax;
  return 0;
}
#include <iostream>
#include <vector>
using namespace std;
int t[11],d[11],l[11];
bool cnt[11];
int n;  
bool dfs(int time,int num){
  if(num == n ) return true;
  for(int i = 0;i < n;i++){
    if(cnt[i] == true){
      if(time > t[i] + d[i]) return false;
      cnt[i] = false;
      bool b = dfs(max(time,t[i]) + l[i],num + 1);
      if(b == true) return true;
      cnt[i] = true;
    }
  }
  return false;
}
void fun(){
  cin>>n;
  for(int i = 0;i < n;i++)  cin>>t[i] >> d[i] >> l[i],cnt[i] = true;
  if(dfs(0,0)){
    cout << "YES" << endl;
  }else{
    cout << "NO" << endl;
  }
}
int main(){
  int T;  cin>> T;
  while(T--){
    fun();
  }
}
#include <iostream>
#include <vector>
using namespace std;
vector<int> arr(10,0);
int main() {
  int n = 0;  cin>>n;
  for(int i = 0;i < n;i++){
    int t;  cin>>t;
    int a = t%10,b = t;
    while(b >= 10){
      b/=10;
    }
    arr[a] = max(arr[a],arr[b] + 1);
  }
  int ans = 0;
  for(int i = 0;i < 10;i++){
    ans = max(ans, arr[i]);
  }
  cout << n - ans << endl;
  return 0;
}
#include <iostream>
#include <string>
#include <unordered_set>
using namespace std;


using namespace std;


int flg[55][55];
int cnt0 = 1000, cnt1 = 2000;
int ans = 0;
bool Find = false;
int m, n;
void add_0(int x, int y) {
	if (x < 0 || y < 0 || x > m + 1 || y > n + 1) return;
	if (flg[x][y] != 0) return;
	flg[x][y] = cnt0;
	if (x == 0 && y == 6) {
		int a = 10;
	}
	add_0(x - 1, y - 1);
	add_0(x - 1, y);
	add_0(x - 1, y + 1);
	add_0(x, y - 1);
	add_0(x, y + 1);
	add_0(x + 1, y - 1);
	add_0(x + 1, y);
	add_0(x + 1, y + 1);
}
bool check(int x, int y) {
	return flg[x - 1][y - 1] == 1000 || flg[x][y - 1] == 1000 || flg[x + 1][y - 1] == 1000 ||
		flg[x - 1][y] == 1000 || flg[x][y] == 1000 || flg[x + 1][y] == 1000 ||
		flg[x - 1][y + 1] == 1000 || flg[x][y + 1] == 1000 || flg[x + 1][y + 1] == 1000;
}
void add_1(int x, int y) {
	if (x < 0 || y < 0 || x > m + 1 || y > n + 1) return;
	if (flg[x][y] != 1) return;
	if (Find == true && check(x, y)) {
		Find = false;
		ans++;
	}
	flg[x][y] = cnt1;
	add_1(x - 1, y);
	add_1(x + 1, y);
	add_1(x, y - 1);
	add_1(x, y + 1);
}
void fun() {
	cin >> m >> n;
	ans = 0;
	cnt0 = 1000, cnt1 = 2000;
	string str;
	for (int i = 1; i <= m; i++) {
		cin >> str;
		for (int j = 1; j <= n; j++)
			flg[i][j] = str[j - 1] - '0';
	}
	for (int i = 0; i <= m; i++) {
		for (int j = 0; j <= n; j++) {
			if (flg[i][j] == 0) {
				add_0(i, j);
				cnt0++;
			}
			if (flg[i][j] == 1) {
				Find = true;
				add_1(i, j);
				cnt1++;
			}
		}
	}
	for (int i = 0; i <= m + 1; i++) {
		for (int j = 0; j <= n + 1; j++)
			flg[i][j] = 0;
	}
	cout << ans << endl;
}
int main() {
	int t;  cin >> t;
	while (t--) {
		fun();
	}
}
#include<iostream>
using namespace std;
char arr[500005];
int n1[500005];
int n2[500005];

int K;
char c1, c2;
int main() {
	cin >> K >> arr >> c1 >> c2;
	unsigned long long ret=0, c=0;
	for (int i = 0, j = K - 1; arr[j] != '\0'; i++, j++) {
		if (arr[i] == c1)
			c++;
		if (arr[j] == c2)
			ret += (c);
	}
	cout << ret << endl;
	return 0;
}
#include <iostream>
#include <set>
using ll = long long;
using namespace std;
	int n, k;
	ll arr[500005];
	class T {
	public:
		bool operator()(const pair<int, ll>& p1,const pair<int, ll>& p2) const{
			if (p1.second == p2.second) {
				return p1.first < p2.first;
			}
			return p1.second < p2.second;
		}
	};
	int main() {
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

		cin >> n >> k;
		set<pair<int,ll>,T> mp;
		
		for (int i = 1; i <= n; i++) {
			cin >> arr[i];
			mp.insert({ i,arr[i]});
		}
		while (k--) {
			int pos = mp.begin()->first;
      ll val = mp.begin()->second;
			int left = pos - 1, right = pos + 1;
			mp.erase(mp.begin());
			arr[pos] = -1;
			while (left > 0 && arr[left] == -1) left--;
			while (right <= n && arr[right] == -1) right++;
			if (left > 0) {
				mp.erase({ left,arr[left] });
				arr[left] += val;
				mp.insert({ left,arr[left] });

			}
			if (right <= n) {
				mp.erase({ right,arr[right] });
				arr[right] += val;
				mp.insert({ right,arr[right] });
			}
		}
		for (int i = 1; i <= n; i++) {
			if (arr[i] != -1) {
				cout << arr[i] << ' ';
			}
		}
		return 0;
	}